package leetcode.editor.cn;

import java.util.Arrays;

/**
题目名字---:下一个排列
题目编号---:31	
解题时间---:2021-09-19 12:06:25
*/
@SuppressWarnings("all")
public class NextPermutation{
    public static void main(String[] args) {
        /**
         * 在计算机科学中，一个原地算法（in-place algorithm）是一种使用小的，
         * 固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部分覆盖掉。
         * 不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。
         */
        Solution solution = new NextPermutation().new Solution();
        int[] ints = {1,3,2};
        solution.nextPermutation(ints);
        System.out.println(ints);
    }

    /**
     * 解法一:暴力法--涉及到回溯算法--46.Permutations
     * @param nums
     */
    public void nextPermutation1(int[] nums) {
        //传进来的就是一个指针
        for (int i = 0; i < nums.length; i++) {
           //涉及全排列--需要用到回溯算法
        }
    }
    /**
     * 解法二: 从后往前找到升子序列--然后确定调整合的子序列的最高位(某一个位置Key)
     * 然后再把后面的序列升序排列
     * @param nums
     */
    public void nextPermutation2(int[] nums) {
        //从后往前找,找到升序的哪一个数字key,就是需要调整的最高位
        int length = nums.length,key=-1;
        for (int i = length-2; i >=0; i--) {
            if (nums[i]<nums[i+1]) {
                key=i;
                break;
            }
        }
        //表示数组是降序排列
        if (key==-1) {
            Arrays.sort(nums);
            return;
        } else {
            int num = nums[key];
            for (int i = key+2; i < nums.length; i++) {
                if (nums[i]<num) {
                    int temp = nums[i-1];
                    nums[i-1] = nums[key];
                    nums[key] = temp;
                }
            }
        }
        //把nums从key之后的元素升序排列
        for (int i = key+1; i < nums.length; i++) {
            for (int j = key+2; j < nums.length; j++) {
                if(nums[i]>nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
       return;
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public void nextPermutation(int[] nums) {
       //传进来的就是一个指针
        //从后往前找,找到升序的哪一个数字key,就是需要调整的最高位
        int length = nums.length,key=-1;
        for (int i = length-2; i >=0; i--) {
            if (nums[i]<nums[i+1]) {
                key=i;
                break;
            }
        }
        //表示数组是降序排列
        if (key==-1) {
            Arrays.sort(nums);
            return;
        } else {
            int num = nums[key];
            for (int i =length-1; i >key ; i--) {
                if (nums[i]>num) {
                    int temp = nums[i];
                    nums[i] = nums[key];
                    nums[key] = temp;
                    continue;
                }
            }
        }
        //把nums从key之后的元素升序排列
        for (int i = key+1; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if(nums[i]>nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}